import java.util.*;

public class Test {
    public static List<Integer> findSubstring1(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int len = words[0].length();
        Map<String,Integer> map = new HashMap<>();
        for(String str : words) {
            map.put(str,map.getOrDefault(str,0) + 1);
        }

        int length = s.length();
        int count = 0;//记录有效数据个数
        int size = words.length;//记录数组的元素总数
        Map<String,Integer> mapS = new HashMap<>();
        for(int left = 0, right = len; right <= length;) {
            String str = s.substring(right - len,right);
            //进窗口
            if(map.containsKey(str)) {
                mapS.put(str, mapS.getOrDefault(str,0) + 1);
                if(map.get(str) >= mapS.get(str)) {
                    count++;
                } else {
                    //去重
                    while(!s.substring(left,left + len).equals(str)) {
                        remove(mapS, len, left, s);
                        left += len;
                        count--;
                    }
                    remove(mapS, len, left, s);
                    left += len;
                }
                right += len;
            }

            //出窗口
            if(!map.containsKey(str)) {
                left = right - len + 1;
                right++;
                count = 0;
                mapS.clear();
            }

            //更新数据
            if(count == size) {
                list.add(left);
                remove(mapS,len,left,s);
                left += len;
                count--;
            }
        }
        return list;
    }

    private static void remove(Map<String,Integer> map, int len, int left, String s) {
        String ss = s.substring(left,left + len);
        map.put(ss,map.get(ss) - 1);
        if(map.get(ss) == 0) {
            map.remove(ss);
        }
    }

    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int len = words[0].length();//记录每个单词的长度
        int size = words.length;//记录单词个数
        Map<String,Integer> mapW = new HashMap<>();
        for(String x : words) {
            mapW.put(x,mapW.getOrDefault(x,0) + 1);
        }

        Map<String,Integer> mapS = new HashMap<>();
        int count = 0; //记录有效单词个数
        int lens = s.length();
        for(int i = 0; i < len; i++) {
            mapS.clear();
            count = 0;
            for(int left = i, right = len + left; right <= lens; right += len) {
                //进窗口
                String ss = s.substring(right - len,right);
                mapS.put(ss,mapS.getOrDefault(ss,0) + 1);

                if(mapW.containsKey(ss)) {
                    if(mapS.get(ss) <= mapW.get(ss)) {
                        count++;
                    } else {
                        //去重 —— 出窗口
                        String s3 = s.substring(left,left+len);
                        while(!s3.equals(ss)) {
                            mapS.put(s3,mapS.get(s3)-1);
                            if(mapS.get(s3) == 0) {
                                mapS.remove(s3);
                            }
                            count--;
                            left+=len;
                            s3 = s.substring(left,left+len);
                        }
                        mapS.put(s3,mapS.get(s3)-1);
                        if(mapS.get(s3) == 0) {
                            mapS.remove(s3);
                        }
                        left+=len;
                    }
                }

                //出窗口
                if(!mapW.containsKey(ss)) {
                    mapS.clear();
                    left = right;
                    count = 0;
                }

                //更新数据
                if(count == size) {
                    list.add(left);
                }
            }
        }
        return list;
    }

    public static String minWindow(String ss, String tt) {
        String str = "";
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        Map<Character,Integer> mapS = new HashMap<>();
        Map<Character,Integer> mapT = new HashMap<>();
        for(char x : t) {
            mapT.put(x,mapT.getOrDefault(x,0)+1);
        }

        int len = s.length;
        int count = 0;
        int size = t.length;
        int minL = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        for(int left = 0, right = 0; right < len; right++) {
            //进窗口
            char x = s[right];
            mapS.put(x,mapS.getOrDefault(x,0)+1);
            if(mapS.get(x) <= mapT.getOrDefault(x,0)) {
                count++;
            }

            //更新数据
            while(count == size) {
                if(right - left + 1 < minL) {
                    start = left;
                    end = right;
                }

                //出窗口
                char del = s[left++];
                if(mapS.get(del) == mapT.getOrDefault(del,0)) {
                    count--;
                }
                mapS.put(del,mapS.get(del) - 1);
            }
        }

        if(minL != Integer.MAX_VALUE) {
            str = ss.substring(start,end+1);
        }
        return str;
    }


    public static void main(String[] args) {
/*        String s = "barfoothefoobarman";
        String[] words = {"foo","bar"};

        List<Integer> list = findSubstring(s,words);
        System.out.println(list);*/

        /*String s = "wordgoodgoodgoodbestword";
        String[] words = {"word","good","best","word"};
        List<Integer> list = findSubstring(s,words);
        System.out.println(list);*/

        /*String s = "aaaaaaaaaaaaaa";
        String[] words = {"aa","aa"};
        List<Integer> list = findSubstring(s,words);
        System.out.println(list);*/
        //System.out.println(minWindow(s, t));
        Arrays.asList(1,2,3);
    }
}
